package com.集合.Collection___.List_.LinkedList双向链表;

@SuppressWarnings("all")
public class LinkedList底层结构模拟 {
    public static void main(String[] args) {
        /**1.LinkedList底层维护的是双向链表；
         * 2.Linked List中维护了两个属性first和last分别指向 首节点和尾节点
         * 3.每个节点（Node对象） 里面有维护了prev ， next ， item 三个属性 ，通过prev指向前一个，next指向后一个节点，最终实现双向链表；
         * 4.添加和删除不是通过数组实现的，所以高效；
         *
         */
        MyNode m1 = new MyNode("第1个元素");  //创建第1个对象
        MyNode m2 = new MyNode("第2个元素");  //创建第2个对象
        MyNode m3 = new MyNode("第3个元素");  //创建第3个对象
        m1.next = m2; //让m1的成员属性next 指向 m2对象；  实现m1的下一个节点是m2；
        m2.next = m3; //让m2的成员属性next 指向 m3对象；  实现m2的下一个节点是m3；
        //下一节点：m1->m2->m3;
        m3.prev = m2; //让m3的成员属prev 指向 m2对象；  实现m3的上一个节点是m2；
        m2.prev = m1; //让m2的成员属性prev 指向 m1对象；  实现m2的下一个节点是m1；
        //上一节点：m3->m2->m1;
        MyNode first = m1;  //让头节点指向最开始的m1
        MyNode last = m3;   //让尾节点指向最后的m4

        while(first != null){
            System.out.println(first);
            first = first.next;
        }
        /**
         * 1.first指向m1 不为空，进入循环，输出m1的内容：第1个元素，让first指向m1的下一个节点m2，
         * 2.first指向m2 不为空，进入循环，输出m2的内容：第2个元素，让first指向m2的下一个节点m3，
         * 3.first指向m3 不为空，进入循环，输出m3的内容：第3个元素，让first指向m3的下一个节点，m3.next为空，就不会再进入循环；，
         */
        System.out.println("===============================================");

        //删除m2，
        m1.next = m2.next;//让m1的下一个节点指向m2的下一个节点m3，即：m1的下一个节点是m3；
        m3.prev = m2.prev;//让m3的上一个节点指向m2的上一个节点m1，即：m3的上一个节点是m1；

        first = m1;
        while(first != null){
            System.out.println(first);
            first = first.next;
        }


        System.out.println("===============================================");

//        新增
        MyNode m4 = new MyNode("add");//创建新的，插入到m1和m3之间；
        m1.next = m4;//让m1的下一个节点指向m4；
        m4.prev = m1;//让m4的上一个节点指向m1；
        m4.next = m3;//让m4的下一个节点指向m3；
        m3.prev = m4;//让m3的上一个节点指向m4；

        first = m1;
        while(first != null){
            System.out.println(first);
            first = first.next;
        }
    }
}

class MyNode {
    Object item;  //用来存放内容的
    MyNode next;  //next成员属性是MyNode对象， 用来存放下一个节点；
    MyNode prev; //prev成员属性是MyNode对象， 用来存放上一个节点； 实际上存放别的对象；

    public MyNode(Object item) {
        this.item = item ;
    }


    public String toString() {
        return  "MyNode name = " + item;
    }
}
